package array.leetcode.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author bruin_du
 * @description 找到所有数组中消失的数字
 * @date 2022/9/18 23:24
 **/
public class Num448_FindDisappearedNumbers {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int index = 0;
        // 原地哈希
        while (index < nums.length) {
            while (nums[index] != nums[nums[index] - 1]) {
                int tmp = nums[index];
                nums[index] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
            index++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] - 1 != i) {
                res.add(i + 1);
            }
        }
        return res;
    }
}
